package com.leetcode.algo;

import org.junit.Test;

import java.util.*;

/**
 *
 *  * @Author :Jaden;
 *  * @TIME :2022/01/11;
 *  * @discription:
 *  给你一个字符串 s，找到 s 中最长的回文子串。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 *
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 *
 * 输入：s = "ac"
 * 输出："a"
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母（大写和/或小写）组成
 */
public class Algo5 {

    /**
     * 思路1：滑动窗口
     */
    public String longestPalindromeV1(String s) {

        // 等于1 直接返回
        if (s.length() == 1) {
            return s;
        }

        // 等于2 判断一下 是不是两个相同的字符
        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) {
                return s;
            } else {
                return String.valueOf(s.charAt(1));
            }
        }

        // s.length >= 3 情况
        String resultStr = "";
        StringBuilder windowStrb = new StringBuilder("");
        for (int i = 0 ; i < s.length() - 1; i++) {
            for (int j = 0 ; j < windowStrb.length() - 1; j++){

            }
        }
        return null;
    }

    /**
     * 思路2：查找不重复的字母下标，<key(长度), valule（ [1,6] 数组）>,
     */
    public String longestPalindromeV2(String s) {

        if (s.length() == 1) {
            return s;
        }

        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) {
                return s;
            }else {
                return String.valueOf(s.charAt(0));
            }
        }

        HashSet set = new HashSet();
        for (int k = 0; k <= s.length() - 1; k++) {
            set.add(s.charAt(k));
        }
        if (set.size() == 1) {
            return s;
        }

        String maxStr = "";
        int length = s.length();

        Set<Character> wordSet = new HashSet();
        Map<Integer, Integer[]> lengthMap = new TreeMap<>(Comparator.reverseOrder());

        for (int i = 0 ; i < length ; i ++) {

                for (int j = i + 1 ; j < length ; j ++) {
                    if (s.charAt(i) == s.charAt(j)) {

                        // 如果该长度已经有值了
                        if (lengthMap.containsKey(j-i)) {

                            // 直接判断 新的值 是不是回文
                            String newStr = s.substring(i, j + 1);

                            // 如果是回文 就用新值把旧值覆盖
                            if (isBackStr(newStr)) {
                                lengthMap.put(j-i, new Integer[] {i, j});
                            }
                        }else {

                            // 该长度没有值，直接插入
                            lengthMap.put(j-i, new Integer[] {i, j});
                        }
                    }
                }
        }

        if (s.length() == wordSet.size()) {
            return String.valueOf(s.charAt(0));
        }

        Set<Map.Entry<Integer, Integer[]>> entrySet = lengthMap.entrySet();
        int notBackStrNum = 0;
        for(Map.Entry<Integer, Integer[]> entry : entrySet){
            Integer lengthKey = entry.getKey();
            Integer[] indexValue = entry.getValue();
            String newMaxStr = s.substring(indexValue[0], indexValue[1] + 1);
            if (isBackStr(newMaxStr)) {
                return newMaxStr;
            }else {
                notBackStrNum++;
            }
        }
        if (entrySet.size() == notBackStrNum) {
            return String.valueOf(s.charAt(0));
        } else {
            return maxStr;

        }
    }

    /**
     * 思路3：老老实实遍历穷举所有字符串，暴力解法
     *
     * 执行用时：
     *      2415 ms 5.00%
     * 内存消耗：
     *      39.3 MB 43.87%

     */
    public String longestPalindromeV3(String s) {


        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) {
                return s;
            }else {
                return String.valueOf(s.charAt(0));
            }
        }
        HashSet set = new HashSet();
        for (int k = 0; k <= s.length() - 1; k++) {
            set.add(s.charAt(k));
        }
        if (set.size() == 1) {
            return s;
        }

        String maxStr = "";
        int length = s.length();
        for(int i = 0; i <= length-1; i++) {
            for (int j = i; j <= length-1; j++) {
                // 切割字符
                String newStr = s.substring(i,j+1);
                if (isBackStr(newStr) & newStr.length() > maxStr.length()) {
                    maxStr = newStr;
                }
            }
        }
        return maxStr;

    }

    public boolean isBackStr(String str) {

        int begin = 0;
        int end = str.length() - 1;

        boolean isBackStrFlag = true;

        while(begin < end | begin + 1 == end) {
            if (str.charAt(begin) != str.charAt(end)) {
                isBackStrFlag = false;
                return isBackStrFlag;
            }
            begin++;
            end--;
        }
        return isBackStrFlag;
    }

    @Test
    public void test() {

        Algo5 algo5 = new Algo5();
        System.out.println(algo5.isBackStr("ccc"));
//        System.out.println(algo5.isBackStr("acbbc1"));
//        System.out.println(algo5.isBackStr("bbbbbbbbb"));
        System.out.println(algo5.longestPalindromeV2("ccc"));

        Map<Integer, Integer> testTree = new TreeMap<>();

        testTree.put(1,100);
        testTree.put(9,100);
        testTree.put(4,100);
        testTree.put(3,100);

        Set<Map.Entry<Integer, Integer>> entrySet = testTree.entrySet();
        for(Map.Entry<Integer, Integer> entry : entrySet){
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println("TreeMap元素的key:"+key+",value:"+value);
        }

        // 1caaac2
    }
}
